<?php
	include_once('./task_func.php');
	include_once('../xml/xml.php');
	class Node
	{
		public $data;
		public $parent;
		public $children;
		function __construct($_data)
		{
			$this->data = $_data;
			$this->parent = NULL;
			$this->children = Array();
		}
		function add_parent($_parent)
		{
			if (is_null($_parent))
				return;

			// Check exist
			if ($this->parent == $_parent)
				return;

			// First, delete this in existing parent's children
			if (!is_null($this->parent) && !is_null($this->parent->children))
			{
				$index = -1;
				for ($i = count($this->parent->children)-1; $i >= 0; $i-- )
					if ($this->parent->children[$i] == $this)
					{
						$index = $i;
						break;
					}
				if ($index >= 0)
					unset($this->parent->children[$index]);
			}

			// Add to new parent;
			$this->parent = $_parent;
			array_push($_parent->children, $this);
		}
		function add_child($_child)
		{
			if (is_null($_child))
				return;
			$_child->add_parent($this);
		}
	}
	class Tree
	{
		public $root;
		public function create_from_list($task_list)
		{
			if (is_null($task_list))
				return;
			$this->sort_task_list(0, count($task_list)-1, $task_list);
			// Create refernce array
			$ref = Array();
			for ($i = count($task_list)-1; $i >= 0; $i--)
				array_push($ref, NULL);
			// Add first member as root
			$this->add_node(NULL, $task_list[0]);
			$ref[0] = $this->root;
			// Add other data
			$len = count($task_list);
			for ($i = 0; $i < $len; $i++)
				if (!is_null($ref[$i]))
				{
					// Find directed children of node
					for ($j = $i+1; $j < $len; $j++)
					{
						$dif = $task_list[$j]->tree_depth - $task_list[$i]->tree_depth;
						if ($dif > 1)
							break;
						if ($dif == 1)
						{
							if (strpos($task_list[$j]->tree_path, $task_list[$i]->tree_path) !== false)
							{
								$node = $this->add_node($ref[$i], $task_list[$j]);
								$ref[$j] = $node;
							}
						}
					}
				}
		}
		public function create_xml()
		{
			$this->do_create_xml($this->root);
		}
		public function print_tree()
		{
			$this->do_print($this->root, 0);
		}
		private function do_print($current, $level)
		{
			if (is_null($current))
				return;
			for ($i = 1; $i <= $level; $i++)
				echo '-';
			echo $current->data->task_name.'<br/>';
			for ($i = 0; $i < count($current->children); $i++)
				$this->do_print($current->children[$i], $level+1);
		}
		private function do_create_xml($current)
		{
			if (is_null($current))
				return;
			XML::start_element("node");
			XML::write_element("task_name", $current->data->task_name);
			XML::write_element("tree_path", $current->data->tree_path);
			XML::write_element("tree_depth", $current->data->tree_depth);
			for ($i = 0; $i < count($current->children); $i++)
				$this->do_create_xml($current->children[$i]);
			XML::end_element();
		}
		private function add_node($object, $data)
		{
			if (is_null($data))
				return false;
			if (is_null($object))
			{
				if (is_null($this->root))
					$this->root = new Node($data);
				else
					return false;
			}
			$node = new Node($data);
			$node->add_parent($object);
			return $node;
		}
		private function sort_task_list($start, $end, &$list)
		{
			if ($start > $end)
				return;
			$x = $start;
			$y = $end;
			$k = (int) (($x + $y) / 2);
			while ($x <= $y)
			{
				while (($list[$x]->tree_depth < $list[$k]->tree_depth) || ($list[$x]->tree_depth == $list[$k]->tree_depth && $list[$x]->tree_path < $list[$k]->tree_path))
					$x++;
				while (($list[$y]->tree_depth > $list[$k]->tree_depth) || (($list[$y]->tree_depth == $list[$k]->tree_depth) && $list[$y]->tree_path > $list[$k]->tree_path))
					$y--;
				if ($x <= $y)
				{
					$z = $list[$x];
					$list[$x] = $list[$y];
					$list[$y] = $z;
					$x++;
					$y--;
				}
			}
			$this->sort_task_list($x, $end, $list);
			$this->sort_task_list($start, $y, $list);
		}
	}

	$test_task_list = array();
	array_push($test_task_list, new Task("B", ".1.2."));
	array_push($test_task_list, new Task("D",".1.4."));
	array_push($test_task_list, new Task("F", ".1.2.6."));
	array_push($test_task_list, new Task("H", ".1.3.8."));
	array_push($test_task_list, new Task("A", ".1."));
	array_push($test_task_list, new Task("C", ".1.3."));
	array_push($test_task_list, new Task("I", ".1.2.6.9."));
	array_push($test_task_list, new Task("G", ".1.3.7."));
	array_push($test_task_list, new Task("K", ".1.3.8.11."));
	array_push($test_task_list, new Task("J", ".1.2.6.10."));
	array_push($test_task_list, new Task("E", ".1.2.5."));
	array_push($test_task_list, new Task("L", ".1.3.8.12."));
	$tree = new Tree();
	$tree->create_from_list($test_task_list);
	XML::start();
	$tree->create_xml();	
	XML::end();
?>